{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Remove to Make Valid Parentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minRemoveToMakeValid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移除无效的括号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <code>'('</code>、<code>')'</code> 和小写字母组成的字符串 <code>s</code>。</p>\n",
    "\n",
    "<p>你需要从字符串中删除最少数目的 <code>'('</code> 或者 <code>')'</code>&nbsp;（可以删除任意位置的括号)，使得剩下的「括号字符串」有效。</p>\n",
    "\n",
    "<p>请返回任意一个合法字符串。</p>\n",
    "\n",
    "<p>有效「括号字符串」应当符合以下&nbsp;<strong>任意一条&nbsp;</strong>要求：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>空字符串或只包含小写字母的字符串</li>\n",
    "\t<li>可以被写作&nbsp;<code>AB</code>（<code>A</code>&nbsp;连接&nbsp;<code>B</code>）的字符串，其中&nbsp;<code>A</code>&nbsp;和&nbsp;<code>B</code>&nbsp;都是有效「括号字符串」</li>\n",
    "\t<li>可以被写作&nbsp;<code>(A)</code>&nbsp;的字符串，其中&nbsp;<code>A</code>&nbsp;是一个有效的「括号字符串」</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"lee(t(c)o)de)\"\n",
    "<strong>输出：</strong>\"lee(t(c)o)de\"\n",
    "<strong>解释：</strong>\"lee(t(co)de)\" , \"lee(t(c)ode)\" 也是一个可行答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"a)b(c)d\"\n",
    "<strong>输出：</strong>\"ab(c)d\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"))((\"\n",
    "<strong>输出：</strong>\"\"\n",
    "<strong>解释：</strong>空字符串也是有效的\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;可能是&nbsp;<code>'('</code>、<code>')'</code>&nbsp;或英文小写字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-remove-to-make-valid-parentheses](https://leetcode.cn/problems/minimum-remove-to-make-valid-parentheses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-remove-to-make-valid-parentheses](https://leetcode.cn/problems/minimum-remove-to-make-valid-parentheses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"lee(t(c)o)de)\"', '\"a)b(c)d\"', '\"))((\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Set\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        remove_pos: Set[int] = set()\n",
    "        stack: List[int] = []\n",
    "            \n",
    "        for i, c in enumerate(s):\n",
    "            if c == \"(\":\n",
    "                stack.append(i)\n",
    "            elif c == \")\":\n",
    "                if len(stack) == 0:\n",
    "                    remove_pos.add(i)\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    \n",
    "        for i in stack:\n",
    "            remove_pos.add(i)\n",
    "            \n",
    "        return \"\".join(s[i] for i in range(len(s)) if i not in remove_pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for index, num in enumerate(s):\n",
    "            if num == \")\":\n",
    "                if stack and stack[-1][1] == \"(\":\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append((index, num))\n",
    "            elif num == \"(\":\n",
    "                stack.append((index, num))\n",
    "\n",
    "        check = set(index for index, num in stack)\n",
    "\n",
    "        arr = \"\"\n",
    "        for index, num in enumerate(s):\n",
    "            if index not in check:\n",
    "                arr += num\n",
    "        return arr\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        result = \"\"\n",
    "        count = []\n",
    "        delcount = []\n",
    "        for index,ch in enumerate(s):\n",
    "            if ch == \"(\":\n",
    "                count.append(index)\n",
    "            elif ch == \")\":\n",
    "                if len(count) == 0:\n",
    "                    delcount.append(index)\n",
    "                else:\n",
    "                    count.pop()\n",
    "        for index, ch in enumerate(s):\n",
    "            if index not in delcount and index not in count:\n",
    "                result += ch\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        if s == \"\":\n",
    "            return s\n",
    "\n",
    "        chr_index = list()\n",
    "        remove_list = list()\n",
    "        length = len(s)\n",
    "        for i in range(0, length):\n",
    "            if s[i] == \"(\":\n",
    "                chr_index.insert(0, i)\n",
    "            elif s[i] == \")\":\n",
    "                if len(chr_index) == 0:\n",
    "                    remove_list.append(i)\n",
    "                else:\n",
    "                    chr_index.pop(0)\n",
    "        for index in chr_index:\n",
    "            remove_list.append(index)\n",
    "        s1 = \"\"\n",
    "        for i in range(0, length):\n",
    "            if i not in remove_list:\n",
    "                s1 += s[i]\n",
    "        return s1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        \n",
    "        st = []\n",
    "        \n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] != ')':\n",
    "                st.append(s[i])\n",
    "            else:\n",
    "                cur = []\n",
    "                while len(st) > 0 and st[-1] != '(':\n",
    "                    cur.append(st[-1])\n",
    "                    del st[-1]\n",
    "                cur = ''.join(cur[::-1])\n",
    "                if len(st) > 0:\n",
    "                    del st[-1]\n",
    "                    st.append('(' + cur + ')')\n",
    "                else:\n",
    "                    st.append(cur)\n",
    "            i += 1\n",
    "        fixed = [i for i in st if i != '(']\n",
    "        return ''.join(fixed)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        ans,stack=[],[]\n",
    "        for i,c in enumerate(s):\n",
    "            if c==')':\n",
    "                if not stack:\n",
    "                    ans.append(i)\n",
    "                else:\n",
    "                    stack.pop()\n",
    "            elif c=='(':\n",
    "                stack.append(i)\n",
    "        ans=ans+stack\n",
    "        for i in ans:\n",
    "            s=s[:i]+'.'+s[i+1:]\n",
    "        return s.replace('.','')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        if s ==\"\":\n",
    "            return s\n",
    "        delete_index = []\n",
    "        left = []\n",
    "        for i,element in enumerate(s):\n",
    "            if element == \"(\":\n",
    "                left.append(i)\n",
    "            if element == \")\" and len(left) >= 1:\n",
    "                left.pop()\n",
    "            elif element == \")\" and len(left) == 0:\n",
    "                delete_index.append(i)\n",
    "        \n",
    "        zuobiao  = sorted(delete_index+left,reverse=True)\n",
    "        for i in zuobiao:\n",
    "            s = s[0:i]+s[i+1:]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        stack = []\n",
    "        result = ''\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == ')':\n",
    "                cur = ''\n",
    "                while stack:\n",
    "                    if stack[-1] == '(':\n",
    "                        cur = stack.pop() + cur + s[i]\n",
    "                        break;\n",
    "                    cur = stack.pop() + cur\n",
    "                stack.append(cur)\n",
    "            else:\n",
    "                stack.append(s[i])\n",
    "        \n",
    "        for i in range(len(stack)):\n",
    "            if stack[i] == '(':\n",
    "                continue\n",
    "            result = result + stack[i]\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        left = []\n",
    "        right = []\n",
    "        res = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                left.append(i)\n",
    "            elif s[i] == ')':\n",
    "                if left:\n",
    "                    left.pop(-1)\n",
    "                else:\n",
    "                    right.append(i)\n",
    "        if len(left) == 0 and len(right) == 0:\n",
    "            return ''.join(res)\n",
    "        all = sorted(left+right, reverse=True)\n",
    "        for j in all:\n",
    "            res.pop(j)\n",
    "        if len(res) == 0:\n",
    "            return ''\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        stack=[]\n",
    "        res=''\n",
    "        for i in s:\n",
    "            if i.isalpha():\n",
    "                res=res+i\n",
    "            elif i==\"(\":\n",
    "                stack.append((res,\"(\"))\n",
    "                res=\"\"\n",
    "            else :\n",
    "                if stack:\n",
    "                    p=stack.pop()\n",
    "                    res=p[0]+p[1]+res+\")\"\n",
    "        while stack:\n",
    "            p=stack.pop()\n",
    "            res=p[0]+res\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minRemoveToMakeValid(self, s):\n",
    "\t\tremove = []\n",
    "\t\tstack = []\n",
    "\t\tfor i, char in enumerate(s):\n",
    "\t\t\tif char == '(':\n",
    "\t\t\t\tstack.append(i)\n",
    "\t\t\telif char == ')':\n",
    "\t\t\t\tif stack:\n",
    "\t\t\t\t\tstack.pop()\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tremove.append(i)\n",
    "\t\tremove = [-1] + remove + stack + [len(s)]\n",
    "\t\tans = ''\n",
    "\t\tfor i in range(len(remove) - 1):\n",
    "\t\t\tans += s[remove[i] + 1: remove[i + 1]]\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        arr=[]\n",
    "        arr1=[]\n",
    "        num=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='(':\n",
    "                arr.append(i)\n",
    "            if s[i]==')' and len(arr)!=0:\n",
    "                arr.pop()\n",
    "            elif  s[i]==')' and len(arr)==0:\n",
    "                arr1.append(i)\n",
    "        for i in arr:\n",
    "            arr1.append(i)\n",
    "        str1=\"\"\n",
    "        for i in range(len(s)):\n",
    "            if i not in arr1:\n",
    "                str1=str1+s[i]\n",
    "        return str1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        index_to_remove = set()\n",
    "        stack = []\n",
    "        for i, char in enumerate(s):\n",
    "            if char not in '()':\n",
    "                continue\n",
    "            if char == '(':\n",
    "                stack.append(i)\n",
    "                continue\n",
    "            if not stack:\n",
    "                index_to_remove.add(i)\n",
    "                continue\n",
    "            stack.pop()\n",
    "        index_to_remove = index_to_remove.union(set(stack))\n",
    "        res = ''\n",
    "        for i, char in enumerate(s):\n",
    "            if i not in index_to_remove:\n",
    "                res += char\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        list_s= list(s)\n",
    "        n = len(list_s)\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if list_s[i] == '(':\n",
    "                stack.append(i)\n",
    "            elif list_s[i] == ')':\n",
    "                if stack and list_s[stack[-1]] == '(':\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(i)\n",
    "        while stack:\n",
    "            list_s.pop(stack.pop())    \n",
    "        return ''.join(list_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        stack = []\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '(':\n",
    "                stack.append((ch, i))\n",
    "            elif ch == ')':\n",
    "                if stack and stack[-1][0] == '(':\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append((ch, i))\n",
    "        \n",
    "        ans_list = list(s)\n",
    "        for _, i in stack:\n",
    "            ans_list[i] = ''\n",
    "        return ''.join(ans_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == \"(\":\n",
    "                stack.append(i)\n",
    "            elif s[i] == \")\":\n",
    "                if stack and s[stack[-1]] == \"(\":\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(i)\n",
    "            i += 1\n",
    "        while stack:\n",
    "            idx = stack.pop()\n",
    "            s = s[:idx] + s[idx+1:]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        res = \"\"\n",
    "        st = []\n",
    "        no = set()\n",
    "        for i, si in enumerate(s):\n",
    "            if si == '(':\n",
    "                st.append(i)\n",
    "            elif si == ')':\n",
    "                if st:\n",
    "                    st.pop()\n",
    "                else:\n",
    "                    no.add(i)\n",
    "        for k in st:\n",
    "            no.add(k)\n",
    "        \n",
    "        for i, si in enumerate(s):\n",
    "            if i in no:\n",
    "                continue\n",
    "            else:\n",
    "                res += si\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        indexes_to_remove = set()\n",
    "        stack = []\n",
    "        for i, c in enumerate(s):\n",
    "            if c not in \"()\":\n",
    "                continue\n",
    "            if c == \"(\":\n",
    "                stack.append(i)\n",
    "            elif not stack:\n",
    "                indexes_to_remove.add(i)\n",
    "            else:\n",
    "                stack.pop()\n",
    "        indexes_to_remove = indexes_to_remove.union(set(stack))\n",
    "        string_builder = []\n",
    "        for i, c in enumerate(s):\n",
    "            if i not in indexes_to_remove:\n",
    "                string_builder.append(c)\n",
    "        return \"\".join(string_builder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        stack, s = [], list(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                stack.append(i)\n",
    "            elif s[i] == ')':\n",
    "                if stack:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    s[i] = \"\"\n",
    "        for i in stack:\n",
    "            s[i] = \"\"\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        k = 0\n",
    "        needDelete = set([])\n",
    "        ## 先删除多余的右括号\n",
    "        for i, v in enumerate(s):\n",
    "            if v != '(' and v != ')':\n",
    "                continue\n",
    "            if v == ')':\n",
    "                if k == 0:\n",
    "                    needDelete.add(i)\n",
    "                else:\n",
    "                    k-=1\n",
    "            else:\n",
    "                k+=1\n",
    "        \n",
    "        ## 后删除多余的左括号\n",
    "        k = 0\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            v = s[i]\n",
    "            if v != '(' and v != ')':\n",
    "                continue\n",
    "            if i in needDelete:\n",
    "                continue\n",
    "            if v == '(':\n",
    "                if k == 0:\n",
    "                    needDelete.add(i)\n",
    "                else:\n",
    "                    k -=1\n",
    "            else:\n",
    "                k+=1\n",
    "        ans = [v for i,v in enumerate(s) if i not in needDelete]\n",
    "        \n",
    "        return ''.join(ans)\n",
    "                \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        invalid = set()\n",
    "        stack = []\n",
    "        n = len(s)\n",
    "        res = []\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == '(':\n",
    "                stack.append(i)\n",
    "            if s[i] == ')':\n",
    "                if not stack:\n",
    "                    invalid.add(i)\n",
    "                else:\n",
    "                    stack.pop()\n",
    "        invalid = invalid | set(stack)\n",
    "        for i in range(n):\n",
    "            if i not in invalid:\n",
    "                res.append(s[i])\n",
    "        \n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        stk = [] #pos of '('\n",
    "        n = len(s)\n",
    "        pos_valid = [True] * n\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                stk.append(i)\n",
    "            elif c == ')':\n",
    "                if not stk:\n",
    "                    pos_valid[i] = False\n",
    "                else:\n",
    "                    stk.pop()\n",
    "        while stk:\n",
    "            pos_valid[stk.pop()] = False\n",
    "                \n",
    "        lst = []\n",
    "        for i, c in enumerate(s):\n",
    "            if pos_valid[i]:    \n",
    "                lst.append(c)\n",
    "        res = \"\".join(lst)\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        left = []\n",
    "        leftCount, rightCount = 0, 0\n",
    "        i = 0\n",
    "        while i<len(s):\n",
    "            if s[i] == '(':\n",
    "                left.append(i)\n",
    "                leftCount+=1\n",
    "            elif s[i] == ')':\n",
    "                if rightCount+1>leftCount:\n",
    "                    s = s[0: i] + s[i+1:]\n",
    "                    continue\n",
    "                else:\n",
    "                    rightCount+=1\n",
    "            i+=1\n",
    "        while leftCount>rightCount:\n",
    "            cur = left.pop()\n",
    "            s = s[0: cur] + s[cur+1:]\n",
    "            leftCount-=1\n",
    "        return s                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        stack = []\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            res.append(s[i])\n",
    "            if s[i] != '(' and s[i] != ')':\n",
    "                continue\n",
    "            if s[i] == '(':\n",
    "                stack.append(i)\n",
    "            elif s[i] == ')' and len(stack) > 0 and s[stack[-1]] == '(':\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(i)\n",
    "        \n",
    "        for i in stack:\n",
    "            res[i] = '-'\n",
    "        return ''.join([ch for ch in res if ch != '-'])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        flag = [True] * n\n",
    "        record = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == \")\":\n",
    "                cnt -= 1\n",
    "                # if cnt == 0:\n",
    "                #     record.pop()\n",
    "                if cnt < 0:\n",
    "                    flag[i] = False\n",
    "                    cnt += 1\n",
    "            if s[i] == \"(\":\n",
    "                cnt += 1\n",
    "                record.append(i)\n",
    "        while cnt:\n",
    "            flag[record[-1]] = False\n",
    "            record.pop()\n",
    "            cnt -= 1\n",
    "        res = \"\"\n",
    "        for i in range(n):\n",
    "            if flag[i]: res += s[i]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        tmp = []\n",
    "        ans = []\n",
    "        cnt = 0\n",
    "        for x in s:\n",
    "            if x == '(':\n",
    "                cnt += 1\n",
    "            if x == ')':\n",
    "                if cnt > 0:\n",
    "                    cnt -= 1\n",
    "                else:\n",
    "                    continue\n",
    "            tmp.append(x)\n",
    "        n = len(tmp)\n",
    "        for x in range(n-1, -1, -1):\n",
    "            if tmp[x] == '(':\n",
    "                if cnt > 0:\n",
    "                    cnt -= 1\n",
    "                    continue    \n",
    "            ans.append(tmp[x])\n",
    "        return \"\".join(ans[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        ans = []\n",
    "        index = []\n",
    "        count = 0\n",
    "        for i,c in enumerate(s):\n",
    "            if c == '(':\n",
    "                index.append(len(ans))\n",
    "                ans.append(c)\n",
    "                count += 1\n",
    "            elif c == ')':\n",
    "                if count > 0:\n",
    "                    ans.append(c)\n",
    "                    count -= 1\n",
    "            else:\n",
    "                ans.append(c)\n",
    "        \n",
    "        for i in range(count):\n",
    "            ans.pop(index[- i - 1])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "import math\n",
    "from typing import List\n",
    "from collections import Counter, deque, defaultdict\n",
    "from bisect import *\n",
    "from heapq import heappop, heappush, heapify\n",
    "from functools import lru_cache\n",
    "from itertools import accumulate, product\n",
    "from sortedcontainers import SortedList\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        pos = []\n",
    "        cur = 0\n",
    "        ans = []\n",
    "        cnt = 0\n",
    "\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                pos.append(cur)\n",
    "                cur += 1\n",
    "                ans.append(c)\n",
    "                cnt += 1\n",
    "            elif c == ')':\n",
    "                if cnt > 0:\n",
    "                    ans.append(c)\n",
    "                    cur += 1\n",
    "                    cnt -= 1\n",
    "            else:\n",
    "                ans.append(c)\n",
    "                cur += 1\n",
    "        i = 1\n",
    "        while cnt > 0:\n",
    "            cnt -= 1\n",
    "            ans.pop(pos[-i])\n",
    "            i += 1\n",
    "\n",
    "        return ''.join(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        sl = list(s)\n",
    "        cntl, cntr = 0, 0\n",
    "        ret = []\n",
    "        for c in s:\n",
    "            if c == \"(\":\n",
    "                cntl += 1\n",
    "            elif c == \")\":\n",
    "                cntr += 1\n",
    "            if c == \")\" and cntr > cntl:\n",
    "                cntr -= 1\n",
    "            else:\n",
    "                ret.append(c)\n",
    "        if cntl > cntr:\n",
    "            left = cntl - cntr\n",
    "            ret2 = []\n",
    "            for c in ret[::-1]:\n",
    "                if c == \"(\" and left > 0:\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    ret2.append(c)\n",
    "            ret = ret2[::-1]\n",
    "        return \"\".join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        list_str=list(s)\n",
    "        odd=0\n",
    "        left=[]\n",
    "        right=[]\n",
    "        delstr=[]\n",
    "        for l,i in enumerate(s):\n",
    "            if i==\"(\":\n",
    "                odd+=1\n",
    "                left.append(l)\n",
    "            elif (i==\")\" and odd>0):\n",
    "                \n",
    "                odd-=1\n",
    "            elif i==\")\" and odd==0:\n",
    "                delstr.append(l)\n",
    "        if odd>0:\n",
    "            for q in range(odd):\n",
    "                delstr.append(left[-1])\n",
    "                del left[-1]\n",
    "        ans=[i for l,i in enumerate(list_str) if l not in delstr]\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        k = []\n",
    "        stack = []\n",
    "        for i,e in enumerate(s):\n",
    "            if e == '(':\n",
    "                stack.append(i)\n",
    "            elif e == ')':\n",
    "                if stack:\n",
    "                    k.append(i)\n",
    "                    k.append(stack.pop())\n",
    "            else:\n",
    "                k.append(i)\n",
    "        k.sort()\n",
    "        ans = []\n",
    "        for j in k:\n",
    "            ans.append(s[j])\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minRemoveToMakeValid(self, s: str) -> str:\n",
    "        left, right, stack, remove = deque(), deque(), deque(), [0 for i in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                left.append(i)\n",
    "            elif s[i] == ')':\n",
    "                right.append(i)\n",
    "        idx_l, idx_r = 0, 0\n",
    "        while (idx_l != len(left) or len(stack) != 0) and idx_r != len(right):\n",
    "            while idx_l != len(left) and right[idx_r] > left[idx_l]:\n",
    "                stack.append(left.popleft())\n",
    "            if len(stack) == 0:\n",
    "                remove[right.popleft()] = 1\n",
    "            else:\n",
    "                stack.pop()\n",
    "                right.popleft()\n",
    "\n",
    "        for i in set(left+right+stack):\n",
    "            remove[i] = 1\n",
    "\n",
    "        ret = \"\"\n",
    "        for i in range(len(s)):\n",
    "            if remove[i] == 0:\n",
    "                ret += s[i]\n",
    "        return ret\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
